/*
 * @Author: szx
 * @Date: 2022-03-24 15:18:33
 * @LastEditTime: 2022-03-24 15:30:08
 * @Description:
 * @FilePath: \leetcode\剑指offer\39\39.js
 */
/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function (nums) {
    const n = Math.floor(nums.length / 2);
    const map = new Map();
    for (let i of nums) {
        map.set(i, (map.get(i) || 0) + 1);
        if (map.get(i) >= n) return i;
    }
};

var majorityElement = function (nums) {
    let vote = 0;
    let prev = nums[0];
    for (let i of nums) {
        if (i == prev) vote++;
        else {
            vote--;
            if (vote < 0) {
                vote = 0;
                prev = i;
            }
        }
    }
    return prev;
};
console.log(majorityElement([2, 2, 1, 1, 1, 2, 2]));
console.log(majorityElement([1, 2, 3, 2, 2, 2, 5, 4, 2]));
